-- -*- mode: Haskell;-*- 
-- Filename:    rlambda.cf 
-- Authors:     lgm                                                    
-- Creation:    Fri May  1 13:17:06 2009 
-- Copyright:   Not supplied 
-- Description: 
--
-- Martin Odersky describes a challenge given by Corky M. :
--
-- Here's the language to to interpret (where postfix * means tupling):

-- Variables: x
-- Integer literals: i
-- Terms:

-- t = Lambda x*. t
--  |  Apply t t*
--  |  Var(x)
--  |  Num(i)

-- We assume usual operational semantics of lambda calculus (i.e. static scoping).

-- The task is to write two interpreters, one with variables x being
-- DeBruijn indices and one with them being names.
-- You should go for maximal sharing, i.e. factor out commonalities into
-- a common class/typeclass/functor/whatever, so that there remains no
-- duplication of code in the two solutions.
--
-- ------------------------------------------------------------------------

Application     . Expression    ::= Expression Expression1                ;
Mention         . Expression1   ::= VariableExpr                          ;
Value           . Expression1   ::= ValueExpr                             ;
Abstraction     . Expression1   ::= "lambda" [VariableExpr] "." Expression1 ;

_               . Expression    ::= Expression1                           ;
_               . Expression1   ::= "(" Expression ")"                    ;

Transcription   . VariableExpr  ::= "@" "<" Expression1 ">"               ;
AtomLiteral     . VariableExpr  ::= Ident                                 ;

Numeric         . ValueExpr     ::= Integer                               ;

[]              . [VariableExpr] ::=                                      ;
(: [])          . [VariableExpr] ::= VariableExpr                         ;
(:)             . [VariableExpr] ::= VariableExpr "," [VariableExpr]      ;

comment "//" ;
comment "/*" "*/" ;
